#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct ListNode
{
    int val;
    struct ListNode* next;
}ListNode;

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    if (list1==NULL)
    {
        return list2;
    }
    if (list2==NULL)
    {
        return list1;
    }
    ListNode* l1 = list1;
    ListNode* l2 = list2;
    ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
    if (phead == NULL)
    {
        perror("malloc");
        exit(1);
    }
    ListNode* ptail = phead;
    while (l1 && l2)
    {
        if (l1->val > l2->val)
        {
            ptail->next = l2;
            l2 = l2->next;
        }
        else
        {
            ptail->next = l1;
            l1 = l1->next;
        }
        ptail = ptail->next;
    }
    if (l1 != NULL)
    {
        ptail->next = l1;
    }
    else
    {
        ptail->next = l2;
    }
    return phead->next;
}
ListNode* ListBuyNode(int x)
{
    ListNode* newnode =(ListNode*) malloc(sizeof(ListNode));
    if (newnode == NULL)
    {
        perror("malloc");
        exit(1);
    }
    newnode->val = x;
    newnode->next = NULL;
    return newnode;
}
int main()
{
    ListNode* list1 = ListBuyNode(1);
    list1->next = ListBuyNode(2);
    list1->next->next = ListBuyNode(4);
    ListNode* list2 = ListBuyNode(1);
    list2->next = ListBuyNode(3);
    list2->next->next = ListBuyNode(4);
    
    ListNode*phead = mergeTwoLists(list1, list2);
    while (phead)
    {
        printf("%d->", phead->val);
        phead = phead->next;
    }
    return 0;
}

//struct ListNode
//{
//    int val;
//    struct ListNode* next;
//};
//
//typedef struct ListNode ListNode;
//
//ListNode* LBuyNode(int x)
//{
//    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
//    if (newnode == NULL)
//    {
//        exit(1);
//    }
//    newnode->val = x;
//    newnode->next = NULL;
//    return newnode;
//}
//ListNode* CreatCircle(int n)
//{
//    ListNode* phead = LBuyNode(1);
//    ListNode* ptail = phead;
//    for (int i = 2; i <= n; i++)
//    {
//        ListNode* newnode = LBuyNode(i);
//        ptail->next = newnode;
//        ptail = ptail->next;
//    }
//    ptail->next = phead;
//    return ptail;
//}
//int ysf(int n, int m) {
//    // write code here
//    ListNode* prev = CreatCircle(n);
//    ListNode* pcur = prev->next;
//    int count = 1;
//    while (pcur->next != pcur)
//    {
//        if (count == m)
//        {
//            prev->next = pcur->next;
//            free(pcur);
//            pcur = prev->next;
//            count = 1;
//        }
//        else
//        {
//            prev = prev->next;
//            pcur = pcur->next;
//            count++;
//        }
//    }
//    return pcur->val;
//}
//int main()
//{
//    //ListNode* phead = CreatCircle(5);
//    //ListNode* pcur = phead->next;
//    //while (pcur != phead)
//    //{
//    //    printf("%d->", pcur->val);
//    //    pcur = pcur->next;
//    //}
//    int ret = ysf(5, 2);
//    printf("%d", ret);
//    return 0;
//}